LeetCode 354. Russian Doll Envelopes 俄罗斯套娃信封问题

Posted on | In

354. Russian Doll Envelopes

题目描述

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Note:
Rotation is not allowed.

示例:

Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3 
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

解答

遇见这种题一上来应该先排一下序，先按照套娃的宽度从小到大排序，如果宽度相同就按照高度从小到大排序。

这样就可以用DP的方法来求解了，DP数组中值最大的就是解（解法1）。

但是这道题还有一道更巧妙的解法：先按照套娃的宽度从小到大排序，如果宽度相同就按照高度从大到小排序。

然后这道题就转换称为高度的最长上升子序列问题（点击查看详解），最长上升子序列的长度就是解（解法2）。

代码

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        if (envelopes.size() == 0) return 0;
        auto n = envelopes.size();
        sort(envelopes.begin(), envelopes.end());
        vector<int> dp(n, 1);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < i; ++j)
                if (envelopes[j].first < envelopes[i].first && envelopes[j].second < envelopes[i].second)
                    dp[i]  = max(dp[i] , dp[j] + 1);
        return *max_element(dp.begin(), dp.end());
    }
};

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        if (envelopes.size() == 0) return 0;
        auto n = envelopes.size();
        vector<int> res;  
        sort(envelopes.begin(), envelopes.end(), [](pair<int, int> a, pair<int, int> b) {
            if (a.first == b.first) return a.second > b.second;
            return a.first < b.first;
        });
        
        for (auto v : envelopes) {
            auto iter = lower_bound(res.begin(), res.end(), v.second);
            if (iter == res.end()) 
                res.push_back(v.second);
            else
                *iter = v.second;
        }
        return res.size();

    }


    
};